﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 031. 最近最少使用缓存❤️
class LRUCache {
public:
	//哈希表定位+双向链表做法
	struct DLinkListNode//手搓链表
	{
		int _key, _value;
		DLinkListNode* _prev;
		DLinkListNode* _next;
		DLinkListNode()
			:_key(0)
			, _value(0)
			, _prev(nullptr)
			, _next(nullptr)
		{}
		DLinkListNode(int key, int value)
			:_key(key)
			, _value(value)
			, _prev(nullptr)
			, _next(nullptr)
		{}
	};
	LRUCache(int capacity)
		:_size(0)
		, _capacity(capacity)
	{
		head = new DLinkListNode();
		tail = new DLinkListNode();
		head->_next = tail;
		tail->_prev = head;
	}

	int get(int key)
	{
		if (!hash.count(key)) return -1;
		DLinkListNode* node = hash[key];
		MoveToHead(node);//访问过就放到头节点
		return node->_value;
	}

	void put(int key, int value)
	{
		if (!hash.count(key))
		{
			DLinkListNode* newnode = new DLinkListNode(key, value);
			_size++;
			hash[key] = newnode;
			AddToHead(newnode);
			if (_size > _capacity)//判断超过容量
			{
				DLinkListNode* removetail = DeleteTail();
				hash.erase(removetail->_key);
				delete removetail;
				--_size;
			}
		}
		else//插入相同key，修改value并且放到头节点
		{
			DLinkListNode* node = hash[key];
			node->_value = value;
			MoveToHead(node);
		}
	}
private:
	int _capacity;
	int _size;
	unordered_map<int, DLinkListNode*>hash;
	DLinkListNode* head;//带头尾哨兵位节点，这样不用判断
	DLinkListNode* tail;
public:
	void AddToHead(DLinkListNode* node)
	{
		node->_prev = head;
		node->_next = head->_next;
		head->_next->_prev = node;
		head->_next = node;
	}
	DLinkListNode* DeleteTail()
	{
		DLinkListNode* node = tail->_prev;
		node->_prev->_next = tail;
		tail->_prev = node->_prev;
		return node;
	}
	void RemoveNode(DLinkListNode* node)
	{
		node->_prev->_next = node->_next;
		node->_next->_prev = node->_prev;
	}
	void MoveToHead(DLinkListNode* node)
	{
		//注意顺序，不能颠倒，否则移除节点找不到前后的节点
		RemoveNode(node);
		AddToHead(node);
	}
};